package com.hardy.data_structure;

/**
 * Author: Hardy
 * Date:   2020/7/5
 * Description:
 **/
public class BinSearch {

    public static void main(String[] args) {
        int[] a = {1, 3, 6, 6, 6, 6, 6, 8, 9, 10};

        System.out.println(search4(a, 7, 0, a.length - 1));
    }

    // 查找第一个等于给定值的元素
    private static int search1(int[] a, int t, int b, int e) {
        if (b >= e && t != a[e]) return e;

        int mid = (b + e) / 2;

        // 恰好相等 之前是不是重复
        if (a[mid] == t) {
            for (; mid >= b && a[mid] == t; mid--) ;
            return mid + 1;
        }

        if (a[mid] > t)
            return search1(a, t, b, mid - 1);
        else
            return search1(a, t, mid + 1, e);
    }

    // 查找最后一个等于给定值的元素
    private static int search2(int[] a, int t, int b, int e) {
        if (b >= e && t != a[e]) return -1;

        int mid = (b + e) / 2;

        // 恰好相等 之前是不是重复
        if (a[mid] == t) {
            for (; mid <= e && a[mid] == t; mid++) ;
            return mid - 1;
        }

        if (a[mid] > t)
            return search2(a, t, b, mid - 1);
        else
            return search2(a, t, mid + 1, e);
    }

    // 查找第一个大于等于给定值的元素
    private static int search3(int[] a, int t, int b, int e) {
        if (b >= e) return e;

        int mid = (b + e) / 2;

        // 恰好相等 之前是不是重复
        if (a[mid] == t) {
            for (; mid >= b && a[mid] == t; mid--) ;
            return mid + 1;
        }

        if (a[mid] > t)
            return search3(a, t, b, mid);
        else
            return search3(a, t, mid + 1, e);
    }

    // 查找最后小于等于给定值的元素
    private static int search4(int[] a, int t, int b, int e) {
        if (b >= e) return e;

        int mid = (b + e) / 2;

        // 恰好相等 之前是不是重复
        if (a[mid] == t) {
            for (; mid <= e && a[mid] == t; mid++) ;
            return mid - 1;
        }

        if (a[mid] > t)
            return search4(a, t, b, mid - 1);
        else
            return search4(a, t, mid, e);
    }
}
